package q768_maxChunksToSorted;

import java.util.Deque;
import java.util.LinkedList;

public class Solution {
    /*
    与769的solution3完全相同的代码
    通过单调栈仍然能够解决该问题
     */
    public int maxChunksToSorted(int[] arr) {
        Deque<Integer> stack = new LinkedList<>();
        stack.addLast(0);

        for (int i = 1; i < arr.length; i++) {
            if (arr[stack.peek()] < arr[i]) {
                stack.push(i);
                continue;
            }

            int max = stack.peek();

            while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
                stack.pop();
            }

            stack.push(max);
        }

        return stack.size();
    }
}
